Boolean function
part 10/24 · 38.8 KB total
──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
The Möbius transform (or Boole–Möbius transform) of a Boolean function is the set of coefficients of its polynomial (algebraic normal form), as a function of the monomial exponent vectors. It is a self-inverse transform. It can be calculated efficiently using a butterfly algorithm ("Fast Möbius Transform"), analogous to the fast Fourier transform.cite-ref-9[9] Coincident Boolean functions are equal to their Möbius transform, i.e. their truth table (minterm) values equal their algebraic (monomial) coefficients.cite-ref-10[10] There are 2^2^(k−1) coincident functions of k arguments.cite-ref-11[11]
Cryptographic analysis